import java.util.Stack;

/*
 * @lc app=leetcode.cn id=84 lang=java
 *
 * [84] 柱状图中最大的矩形
 *
 * https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
 *
 * algorithms
 * Hard (44.29%)
 * Likes:    1975
 * Dislikes: 0
 * Total Accepted:    255.8K
 * Total Submissions: 577.2K
 * Testcase Example:  '[2,1,5,6,2,3]'
 *
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 
 * 
 * 
 * 示例 1:
 * 
 * 
 * 
 * 
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 
 * 
 * 示例 2：
 * 
 * 
 * 
 * 
 * 输入： heights = [2,4]
 * 输出： 4
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * 0 
 * 
 * 
 */

// @lc code=start
class Solution {

    // 单调栈 + 常数优化
    public int largestRectangleArea(int[] height) {
        int n = height.length;
        // 放索引
        Stack<Integer> stack = new Stack<>();
        int[] leftNextLess = new int[n], rightNextLess = new int[n];
        Arrays.fill(rightNextLess, n);

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
                // 左边界弹出时，可计算右边界
                rightNextLess[stack.peek()] = i;
                stack.pop();
            }
            leftNextLess[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer = Math.max(answer, (rightNextLess[i] - leftNextLess[i] - 1) * height[i]);
        }
        return answer;
    }

    public int largestRectangleArea3(int[] height) {
        int n = height.length;
        // 放索引
        Stack<Integer> stack = new Stack<>();
        int[] leftNextLess = new int[n], rightNextLess = new int[n];

        // 右边界
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
                stack.pop();
            }
            rightNextLess[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        stack.clear();
        // 左边界
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
                stack.pop();
            }
            leftNextLess[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer = Math.max(answer, (rightNextLess[i] - leftNextLess[i] - 1) * height[i]);
        }
        return answer;
    }

    public int largestRectangleArea2(int[] heights) {
        int area = 0;
        // 固定底，找最小高
        for (int left = 0; left < heights.length; left++) {
            int minHeight = Integer.MAX_VALUE;
            for (int right = left; right < heights.length; right++) {
                minHeight = Math.min(minHeight, heights[right]);
                area = Math.max(area, (right - left + 1) * minHeight);
            }

        }
        return area;
    }

    public int largestRectangleArea1(int[] heights) {
        // 最大面积， 固定底，找最大高，或者 固定高，找最大底。
        // 固定高更简单一些。
        // 固定高，找最大底
        int area = 0;
        for (int i = 0; i < heights.length; i++) {
            int right = i;
            int left = i;
            while (right < heights.length - 1 && heights[i] <= heights[right + 1]) {
                right++;
            }
            while (left > 0 && heights[i] <= heights[left - 1]) {
                left--;
            }
            area = Math.max(area, heights[i] * (right - left + 1));
        }
        return area;
    }

}
// @lc code=end
